package cn.edu.jxau.test;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Objects;

/**
 * 海量数据(有重复)找中位数
 * 
 * @author Fudashi
 */
public class Main {

	private static final int MAX_ARR_LEN = 100;

	public static void main(String[] args) throws IOException {
		int kth = median(new File("C:\\Users\\Fudashi\\Desktop\\data.txt"), 1000);
		System.out.println(kth);
	}

	public static int median(File file, long length) throws IOException {

		// 参数校验 //
		Objects.requireNonNull(file, "参数file不能为null");
		if (!file.exists()) {
			throw new IOException("文件不存在");
		}
		if (file.isDirectory()) {
			throw new IOException("不可以是文件夹");
		}
		if (!file.canRead()) {
			throw new IOException("文件不可读");
		}
		return kth(file, length, Integer.SIZE - 1, length / 2);
	}

	private static int kth(File file, long fileLen, int n, long k) throws IOException {

		if (fileLen <= MAX_ARR_LEN) {
			int[] arr = new int[(int) fileLen];
			try (FileInputStream fileIn = new FileInputStream(file); DataInputStream in = new DataInputStream(fileIn)) {
				for (int i = 0; i < fileLen; i++) {
					arr[i] = in.readInt();
				}
			} catch (IOException e) {
				throw new IOException("文件读取失败");
			}
			Arrays.sort(arr);
			return arr[(int) k];
		}
		int len0 = 0;
		int len1 = 0;
		// 1.将file中的数据根据n位放入两个临时文件中 //
		File file0 = File.createTempFile(n + "_0", null);
		File file1 = File.createTempFile(n + "_1", null);
		try (FileInputStream fileIn = new FileInputStream(file);
				FileOutputStream fileOut0 = new FileOutputStream(file0);
				FileOutputStream fileOut1 = new FileOutputStream(file1);
				DataInputStream in = new DataInputStream(fileIn);
				DataOutputStream out0 = new DataOutputStream(fileOut0);
				DataOutputStream out1 = new DataOutputStream(fileOut1);) {
			for (long i = 0; i < fileLen; i++) {
				int num = in.readInt();
				if ((num >> n & 1) == 0) {
					out0.writeInt(num);
					len0++;
				} else {
					out1.writeInt(num);
					len1++;
				}
			}
		} catch (IOException e) {
			throw new IOException("文件读写异常", e);
		}
		// 2.选择kth所在的文件执行进行kth()方法 //
		if (n == Integer.SIZE - 1) {// file1中的数据小于file0中的数据
			if (len1 <= k) {
				return kth(file0, len0, n - 1, k - len1);
			} else {
				return kth(file1, len1, n - 1, k);
			}
		} else { // file0中的数据小于file1中的数据
			if (len0 > k) {
				return kth(file0, len0, n - 1, k);
			} else {
				return kth(file1, len1, n - 1, k - len0);
			}
		}
	}
}